/*
 * @Author: lei
 * @Description: 树的前中后序遍历的递归和非递归写法 以及 层次遍历
 * @FilePath: /树/traverse.cc
 */
#include <queue>
#include <stack>
#include <vector>

#include "definition.h"

// how to design a Recursion
// 1. design the recursion function prototype
// 2. find the baseline
// 3. complete things in a single level
void PreorderTraverse1(TreeNode* cur, std::vector<int>& vec) {
  if (!cur) return;
  vec.push_back(cur->val);
  PreorderTraverse1(cur->left, vec);
  PreorderTraverse1(cur->right, vec);
}
void InorderTraversal1(TreeNode* cur, std::vector<int>& vec) {
  if (cur == nullptr) return;
  InorderTraversal1(cur->left, vec);   // 左
  vec.push_back(cur->val);             // 中
  InorderTraversal1(cur->right, vec);  // 右
}
void PostorderTraverse1(TreeNode* cur, std::vector<int>& vec) {
  if (!cur) return;
  PostorderTraverse1(cur->left, vec);
  PostorderTraverse1(cur->right, vec);
  vec.push_back(cur->val);
}
void LevelTraverse(TreeNode* root, std::vector<int>& vec) {
  queue<TreeNode*> que;
  que.push(root);
  while (!que.empty()) {
    TreeNode* temp = que.front();
    que.pop();
    vec.push_back(temp->val);
    if (temp->left) que.push(temp->left);
    if (temp->right) que.push(temp->right);
  }
}
void PreorderTraverse2(TreeNode* cur, std::vector<int>& vec) {
  stack<TreeNode*> st;
  st.push(cur);
  while (!st.empty()) {
    TreeNode* temp = st.top();
    st.pop();
    vec.push_back(temp->val);
    if (temp->right) st.push(temp->right);
    if (temp->left) st.push(temp->left);
  }
}
// ***************************
void InorderTraversal2(TreeNode* root, std::vector<int>& vec) {
  stack<TreeNode*> st;
  TreeNode* cur = root;
  while (cur || !st.empty()) {
    while (cur) {
      st.push(cur);
      cur = cur->left;  // 左
    }
    if (!st.empty()) {
      cur = st.top();  // 中
      vec.push_back(cur->val);
      st.pop();
      cur = cur->right;  // 右
    }
  }
}

void PostorderTraverse2(TreeNode* cur, std::vector<int>& vec) {
  stack<TreeNode*> st;
  stack<int> value;
  st.push(cur);
  while (!st.empty()) {
    TreeNode* temp = st.top();
    st.pop();
    value.push(temp->val);
    if (temp->left) st.push(temp->left);
    if (temp->right) st.push(temp->right);
  }
  while (!value.empty()) {
    vec.push_back(value.top());
    value.pop();
  }
}
// TODO：统一风格的三种遍历的迭代写法